package pathfinding
{
	import flash.utils.getTimer;

	//from AdvancED ActionScript 3.0 Animation by Keith Peters
	
	public class AStar
	{
		private var _open:Array;

		private var _closed:Array;

		private var _grid:Grid;

		private var _endNode:Node;

		private var _startNode:Node;

		public var _path:Array;
		private var _heuristic:Function = manhattan;
//		private var _heuristic:Function = euclidian;
//		private var _heuristic:Function = diagonal;
		private var _straightCost:Number = 1.0;
		private var _diagCost:Number = Math.SQRT2;
		
		/** 支持8方向与4方向寻路 **/
		private var _isDir8:Boolean = true;

		public function AStar()
		{
		}

		
		private var _tracker:PathFinding;
		
		public function findPath(grid:Grid, isSmooth:Boolean = false, isDir8:Boolean = true, tracker:PathFinding = null ):Boolean
		{
			_grid = grid;
			_open = new Array();
			_closed = new Array();
			_startNode = _grid.startNode;
			_endNode = _grid.endNode;
			_startNode.g = 0;
			_startNode.h = _heuristic(_startNode);
			_startNode.f = _startNode.g + _startNode.h;
			
			_isDir8 = isDir8;
			
			
			if( tracker )
			{
				_tracker = tracker;
			
				_tracker.init( grid );
			}
			
			//return search();
			
			 if( isSmooth )
			{
				return searchSmooth();
			}
			else
			{
				return search();
			}
		}

		public function search():Boolean
		{
			var node:Node = _startNode;
		
			while (node != _endNode)
			{
				var startX:int = Math.max(0, node.x - 1);
				var endX:int = Math.min(_grid.numCols - 1, node.x + 1);
				
				var startY:int = Math.max(0, node.y - 1);
				var endY:int = Math.min(_grid.numRows - 1, node.y + 1);
				
				for (var i:int = startX; i <= endX; i++)
				{
					
					for (var j:int = startY; j <= endY; j++)
					{
						
						if ( !_isDir8 && Math.abs(i-node.x) == 1 && Math.abs(j-node.y) == 1 )
						{//此处用于防止斜线寻路
						  continue;	
						}
						
						var test:Node = _grid.getNode(i, j);
						
						_tracker.visitNode( test );
						
						if( isClosed( test ) )
						{  
							if( _tracker )
							{
								_tracker.pushNodeClose( test );
							}
							continue;
						}
						
						if ( ( test == node || !isWalkable( test, node ) ) && ( test.x != this._grid.endNode.x ||  test.y != this._grid.endNode.y ) )
						{
							if( test == node )
							{
								_tracker.popNodeOpen( test );
							}else if( !test.walkable )
							{
								_tracker.unWalkable( test );
							}
							else if( this.isOpen( test ) )
							{
								_tracker.pushNodeOpen( test );
							}
							else
							{
								_tracker.pushNone( test );
							}
							
							
							continue;
						}
						var cost:Number = _straightCost;
						if (!((node.x == test.x) || (node.y == test.y)))
						{
							cost = _diagCost;
						}
						
						var g:Number = node.g + cost * test.costMultiplier;
						var h:Number = _heuristic(test);
						var f:Number = g + h;
						if (isOpen(test) || isClosed(test))
						{
							if (test.f > f)
							{
								test.f = f;
								test.g = g;
								test.h = h;
								test.parent = node;
							}
							
							if( _tracker )
							{
								_tracker.pushNodeOpen( test );
							}
						}
						else
						{
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
							_open.push(test);
							
							if( _tracker )
							{
								_tracker.pushNodeOpen( test );
							}
						}
					}
				}
				
				
				/*
				for (var o:int = 0; o < _open.length; o++)
				{
				}
				*/
				
				//_closed.push(node);
				
				pushClosed( node );
				
				if( _tracker )
				{
					_tracker.pushNodeClose( node );
				}
				
				if (_open.length == 0)
				{
//					trace("no path found", _startNode.x, _startNode.y, _endNode.x, _endNode.y);
					if( _tracker )
					{
						_tracker.unFind();
					}
					return false;
				}
				
				//通过排序获得最小节点至少也要O(nLogn), 直接查找最小数是o(n),如果用二叉堆是o(1),插入新节点o(logn),暂时性能占用不大的情况下,先用o(n)的方法
				//_open.sortOn("f", Array.NUMERIC);
				//node = _open.shift() as Node;
				
				
				node = _open[0];
				
				var t_minIndex:int = 0;
				
				for( var o:int = 1; o < _open.length; o++ )
				{
					if( node.f > Node( _open[o] ).f )
					{
						node = _open[o];
						
						t_minIndex = o;
					}
				}
				
				_open.splice( t_minIndex, 1 );
				
				if( _tracker /*&& !isClosed( node )*/ )
				{
					_tracker.popNodeOpen( node );
				}
			}
			
			buildPath();
			
			if( _tracker )
			{
				_tracker.find();
			}
			
			return true;
		}
		
		private function searchSmooth():Boolean
		{
			var result:Boolean = false;
			
			if( canGoStraight( _startNode.x, _startNode.y, _endNode.x, _endNode.y ) )
			{
				_path = [ _endNode ];
				
				result = true;
			}
			else
			{
				result = search();
				
				if( result )
				{
					buildSmoothPath();
				}
			}
			
			
			return result;
		}
		
		private function canGoStraight( sX:Number, sY:Number, eX:Number, eY:Number ):Boolean
		{
			var t_diffX:int = eX - sX;
			
			var t_diffY:int = eY - sY;
			
			var t_moveDirX:int;
			
			var t_moveDirY:int;
			
			var testNode:Node;
			
			var lastNode:Node = _grid.getNode( sX, sY );
			
			if( t_diffX == 0 )
			{
				t_moveDirY = t_diffY > 0 ? 1 : -1
				
				while( sY != eY )
				{
					sY += t_moveDirY;
					
					testNode = _grid.getNode( sX, sY );	
					
					if( !isWalkable( testNode, lastNode ) )
					{
						return false;	
					}
					
					lastNode = testNode;
				}
				
				return true;
			}
			else if( t_diffY == 0 )
			{
				t_moveDirX = t_diffX > 0 ? 1 : -1
				
				while( sX != eX )
				{
					sX += t_moveDirX;
					
					testNode = _grid.getNode( sX, sY );	
					
					if( !isWalkable( testNode, lastNode ) )
					{
						return false;	
					}
					
					lastNode = testNode;
				}
				
				return true;
				
			}
			
			//不支持8方向寻路,则无需继续判断斜线路径
			if( !_isDir8 ) return false;
			
			var t_absDiffX:int = t_diffX > 0 ? t_diffX : -t_diffX;
			
			var t_absDiffY:int = t_diffY > 0 ? t_diffY : -t_diffY;
			
			if( t_absDiffX == t_absDiffY )
			{
				t_moveDirX = t_diffX > 0 ? 1 : -1
					
				t_moveDirY = t_diffY > 0 ? 1 : -1
				
				while( sX != eX )
				{
					sX += t_moveDirX;
					
					sY += t_moveDirY;
					
					testNode = _grid.getNode( sX, sY );	
				
					if( !isWalkable( testNode, lastNode ) )
					{
						return false;	
					}
					
					lastNode = testNode;
				}
				
				return true;
			}
			
			var t_lowerMove:Number;
			
			//与格子交叠面积小于该百分比时,不判断格子通行性
			var t_testRate:Number = 0.1;
			
			if (t_absDiffX > t_absDiffY)
			{
				t_moveDirX = t_diffX < 0 ? -1 : 1;
				
				t_lowerMove = t_diffY / t_absDiffX;
				
				while ( sX != eX )
				{
					
					sX = sX + t_moveDirX;
					
					sY = sY + t_lowerMove;
					
					if( t_lowerMove > 0 )
					{
						testNode = _grid.getNode( sX, sY + t_testRate );
					}
					else
					{
						testNode = _grid.getNode( sX, sY + ( 1 - t_testRate )  );
					}
					
					//当前Y坐标与某格有交叠,且交叠面积小于格子高度的1%,则不判断该格的通行性. ( 交叠比例的判断分上下两种情况 ) 
					if ( !_grid.getNode( sX, sY + ( 1 - t_testRate ) ).walkable || !_grid.getNode( sX, sY + t_testRate ).walkable || !isWalkable( testNode, lastNode )  )
					{
						return false;
					}
					
					
					lastNode = testNode;
				}
				return true;
			}
			else
			{
				t_lowerMove = t_diffX / t_absDiffY;
				
				t_moveDirY = t_diffY < 0 ? -1 : 1;
				
				while( sY != eY )
				{
					
					sX = sX + t_lowerMove;
					
					sY = sY + t_moveDirY;
					
					if( t_lowerMove > 0 )
					{
						testNode = _grid.getNode( sX + ( 1 - t_testRate ), sY  );
					}
					else
					{
						testNode = _grid.getNode( sX + t_testRate, sY );
					}
					
					//当前X坐标与某格有交叠,且交叠面积小于格子宽度的1%,则不判断该格的通行性. ( 交叠比例的判断分左右两种情况 ) 
					if ( !_grid.getNode( sX + ( 1 - t_testRate ), sY ).walkable || !_grid.getNode( sX + t_testRate, sY ).walkable || !isWalkable( testNode, lastNode )  )
					{
						return false;
					}
					
					lastNode = testNode;
				}
				
			}
			
			return true;
			
		}
		

		private function buildPath():void
		{
			_path = new Array();
			var node:Node = _endNode;
			_path.push(node);
			while ( node && node != _startNode)
			{
				node = node.parent;
				_path.unshift(node);
			}
		}

		
		private function buildSmoothPath():void
		{
			var t_startNode:Node = _startNode;
			
			var t_endNode:Node;
			
			var newPath:Array = [];
			
			var t_lastNode:Node;
			
			for( var i:int = 0; i < _path.length; i++ )
			{
				var t_curNode:Node = _path[i] as Node;
				
				if( canGoStraight( t_startNode.x, t_startNode.y, t_curNode.x,  t_curNode.y ) )
				{
					t_endNode = t_curNode;
					
					continue;
				}
				
				newPath.push( t_endNode );
				
				t_startNode = t_endNode;
				
				t_endNode = t_curNode;
								
			}
			
			newPath.push( t_endNode );
			
			_path = newPath;
		}
			
		private function manhattan(node:Node):Number
		{
			if(!node || !_endNode)
			{
				return Number.MAX_VALUE;
			}
			return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y + _endNode.y) * _straightCost;
		}

		
		private function euclidian(node:Node):Number
		{
			var dx:Number = node.x - _endNode.x;
			var dy:Number = node.y - _endNode.y;
			return Math.sqrt(dx * dx + dy * dy) * _straightCost;
		}

		private function diagonal(node:Node):Number
		{
			var dx:Number = Math.abs(node.x - _endNode.x);
			var dy:Number = Math.abs(node.y - _endNode.y);
			var diag:Number = Math.min(dx, dy);
			var straight:Number = dx + dy;
			return _diagCost * diag + _straightCost * (straight - 2 * diag);
		}
		
		private function pushClosed( n:Node ):void
		{
			var key:int = n.x + _grid.numCols * n.y;
			
			_closed[key] = true;
		}
		
		private function isClosed(node:Node):Boolean
		{
			var key:int = node.x + _grid.numCols * node.y;
			
			return _closed[key];
			
			//return _closed.indexOf(n) != -1;
		}
		
		private function isOpen(n:Node):Boolean
		{
			return _open.indexOf(n) != -1;
		}
		
		/**
		 * 额外通行判断,除了判断test节点本身的通行情况外,额外根据当前节点node与test的位置关系进行一些判断.
		 * 
		 * 当前仅判断如果是以下这种情况, 则不可通行:<br>
		 * 	
		 * 		<li>▲:表示不通行的节点</li>
		 *  	<li>☆:表示test的节点</li>
		 *  	<li>◇:表示node的节点</li>
		 * 	 <br><br>
		 * 
		 *   ☆▲☆<br>
		 *   ▲◇▲<br>
		 *   ☆▲☆
		 * 		
		 * 
		 * @return 
		 * 
		 */		
		private function isWalkable( test:Node, node:Node ):Boolean
		{
			return	test.walkable && _grid.getNode( node.x, test.y).walkable && _grid.getNode( test.x, node.y).walkable;
		}
	}
}